#include <pmm.h>
#include <list.h>
#include <string.h>
#include <default_pmm.h>
#include <stdio.h>

#define LEFT_LEAF(index) ((index) * 2 + 1)
#define RIGHT_LEAF(index) ((index) * 2 + 2)//用于获取二叉树的左叶子结点和右叶子结点
#define PARENT(index) ( ((index) + 1) / 2 - 1)//获得二叉树的父结点
#define IS_POWER_OF_2(x) (!((x)&((x)-1)))//判断它是不是二的幂
unsigned calculate_node_size(unsigned n) {//用于计算大于等于n的最小的2的幂
    unsigned i = 0;
    n--;
    while (n >= 1) {
        n >>= 1; 
        i++;
    }//这个循环就是每次将n除以2，直到n小于1为止
    return 1 << i; //将1左移i位，就相当于1乘以了2的i次幂
}
free_area_t free_area;//管理内存空闲区域
#define max(a, b) ((a) > (b) ? (a) : (b))//一个宏，用于计算最大值
#define free_list (free_area.free_list)//简化了访问free_area的数据成员free_list
#define nr_free (free_area.nr_free)//同上，对nr_free的简化访问
unsigned *root;//保存伙伴系统的树结构
int size;//表示伙伴系统树的大小
struct Page *_base;//指向伙伴系统管理的内存块的起始地址

static void
buddy_system_init(void)//初始化伙伴系统的空闲链表，并将 nr_free 设置为0，表示当前没有空闲页面。
{
    list_init(&free_list);
    nr_free = 0;
}

static void
buddy_system_init_memmap(struct Page *base, size_t n)//初始化内存块并设置伙伴系统的初始状态
{
    assert(n > 0);
    //初始化基础页结构，遍历从base开始的每一页
    struct Page *p = base;
    for (; p != base + n; p++)
    {
        assert(PageReserved(p));//断言成预留状态
        p->flags = p->property = 0;//标志页和属性都设置为0，表明没有特殊的页和属性
        set_page_ref(p, 0);//页的引用也为0
        SetPageProperty(p);//页的属性设置为可用状态
    }
    base->property = n;//将base的property属性设置为n，表名从base开始有n个连续的空闲页面
    SetPageProperty(base);//将该页标志为具有属性
    nr_free += n;//现在系统新增了n个空闲页面
    //初始化二叉树的结构
    _base = base;//内存管理的起始位置
    size =calculate_node_size(n);//计算与管理的页数相关的树的节点数
    unsigned node_size = 2*size;//node_size被设置成树的根节点所对应的内存块大小（2倍的size），这个node_size是之后循环的时候会用的。
    root = (unsigned *)(base + size);//root数组中，每个节点的值被初始化为其代表的内存块的大小，如果为0表示已经分配出去了
    for (int i = 0; i < 2 * size - 1; ++i)//每当索引i+1是2的幂的时候，将node_size的值减半，因为在二叉树中，每个节点代表的内存块大小是它父节点的一半
    {
        if (IS_POWER_OF_2(i + 1))
            node_size /= 2;
        root[i] = node_size;
    }
}

static struct Page *
buddy_system_alloc_pages(size_t n)//分配内存页面
{
    assert(n > 0);
    if (n > nr_free)
    {
        return NULL;
    }//如果请求的页数大于当前空闲的页数，则返回。
    struct Page *page = NULL;//指向分配的页面
    unsigned index = 0;//从根节点开始查找
    unsigned node_size;//追踪当前管理的内存块的大小
    unsigned offset = 0;//偏移量，计算分配的内存块在物理内存中的位置
    if (n <= 0)
        n = 1;
    else if (!IS_POWER_OF_2(n))//如果不是2的整数幂，即改成大于等于它的最小的2的整数幂
    {
        n = calculate_node_size(n);
    }
    if (root[index] < n)//如果二叉树根节点（索引 0）表示的内存块小于请求的大小 n，则偏移量为-1，表示无法成功
        offset = -1;
    for (node_size = size; node_size != n; node_size /= 2)//从根节点开始查找，逐步向下遍历二叉树的节点：
        //如果左子节点的内存块大小 root[LEFT_LEAF(index)] 大于等于 n，则选择左子节点（LEFT_LEAF(index)）。
        //否则选择右子节点（RIGHT_LEAF(index)）。
        //这样不断向下直到找到满足条件的块，node_size 随着层级下降而减半。
    {
        if (root[LEFT_LEAF(index) ] >= n)
            index =LEFT_LEAF(index) ;
        else
            index =RIGHT_LEAF(index) ;
    }
    root[index] = 0;//找到了之后将其设置为0，表示已经分配出去了。
    offset = (index + 1) * node_size - size;//// 计算偏移量，根据当前节点在二叉树中的位置和块大小计算偏移。
    while (index > 0)
    {
       index=PARENT(index);
        root[index]=max(root[LEFT_LEAF(index)],root[RIGHT_LEAF(index)]);
    }//向上回溯更新二叉树的父节点，保证父节点的值始终是其左右子节点中最大的可用块的大小。是为了维护二叉树的内存块状态，使得下一次分配时，仍能快速找到合适的块。
    page = _base+ offset;//_base 是内存的起始地址，通过计算的 offset 计算出分配的页面指针 page。
    unsigned size_ = calculate_node_size(n);//再次计算实际分配的块大小，以确保分配的块大小是 2 的幂。
    nr_free -= size_;//更新系统的空闲页面计数 nr_free，从中减去实际分配的内存块大小。
    for (struct Page *p = page; p != page + size_; p++)//清空分配的所有页面的属性标志，表示这些页面已经不再是空闲的。
        ClearPageProperty(p);
    page->property = n;//设置起始页面的 property 属性为 n，表示分配了 n 个页面的块
    return page;
}

static void
buddy_system_free_pages(struct Page *base, size_t n)//释放内存页面
{
    assert(n > 0);//确保n是大于0的
    n=calculate_node_size(n);//n调成大于等于n的最小的2的幂
    struct Page *p = base;//获取要释放的起始页
    for (; p != base + n; p++)//遍历所有将要释放的页面，确保它们不是保留页且没有其他特殊属性。然后通过 set_page_ref(p, 0) 将页面引用计数清零，表明这些页面不再被使用。
    {
        assert(!PageReserved(p) && !PageProperty(p));
        set_page_ref(p, 0);
    }
    nr_free += n;//更新系统中的空闲页面计数，将 n 个释放的页面重新计入 nr_free，表示系统有更多的空闲内存可用。
    unsigned offset = base - _base;//计算要释放的内存块在二叉树结构中的偏移量 offset。base 是要释放的页面指针，_base 是内存管理的起始地址，offset 表示该块相对于内存起始地址的偏移。
    unsigned node_size = 1;//设置 node_size 为 1，表示开始处理的是最小单位的内存块。
    unsigned index = size + offset - 1;//index 计算出这个内存块在二叉树中的位置。size 是二叉树的大小，而 offset 和 size 用来计算内存块在树中的节点索引。
    //在伙伴系统的二叉树中查找空闲的内存块，并且尝试合并与之相邻的伙伴块。
    //Buddy System 二叉树向上查找，尝试找到一个可释放的内存块的父节点，直到找到一个没有被占用的节点
    while(root[index]){
        node_size *= 2;
        if (index == 0)
            return;
        index=PARENT(index);
    }
    root[index] = node_size;//如果找到空闲块，更新 root[index]，表示释放的块大小为 node_size。这一行意味着此节点已经被释放并设置为相应的大小。
    while (index)
    {
        index=PARENT(index);
        node_size *= 2;
        if (root[LEFT_LEAF(index)] + root[RIGHT_LEAF(index)] == node_size)
            //如果当前节点的左右子节点 root[LEFT_LEAF(index)] 和 root[RIGHT_LEAF(index)] 加起来正好等于 node_size，说明两个子节点的块可以合并，设置父节点 root[index] 为合并后的块大小。
            root[index] = node_size;
        else
            root[index]=max(root[LEFT_LEAF(index)],root[RIGHT_LEAF(index)]);//否则，父节点 root[index] 的值设为左右子节点中较大的块，这保证二叉树能正确反映当前系统中最大的空闲块。
    }
}

static size_t
buddy_system_nr_free_pages(void)//获取空闲页面数
{
    return nr_free;
}
static void
buddy_check(void)//测试函数
{
    struct Page *p0, *A, *B, *C, *D;
    p0 = A = B = C = D = NULL;
    A = alloc_pages(70);
    B = alloc_pages(35);
    C = alloc_pages(257);
    D = alloc_pages(63);
    cprintf("A分配70，B分配35，C分配257，D分配63\n");
    cprintf("此时A %p\n",A);
    cprintf("此时B %p\n",B);
    cprintf("此时C %p\n",C);
    cprintf("此时D %p\n",D);
        
    free_pages(B, 35);
    cprintf("B释放35\n");
    free_pages(D, 63);
    cprintf("D释放63\n");
    cprintf("此时BD应该合并\n");
    free_pages(A, 70);
    cprintf("A释放70\n");
    cprintf("此时前512个已空，我们再分配511个的A来测试\n");
    A = alloc_pages(511);
    cprintf("A分配511\n");
    cprintf("此时A %p\n",A);
    free_pages(A, 512);
    cprintf("A释放512\n");

    A = alloc_pages(255);
    B = alloc_pages(255);
    cprintf("A分配255，B分配255\n");
    cprintf("此时A %p\n",A);
    cprintf("此时B %p\n",B);
    free_pages(C, 257);
    free_pages(A, 255);
    free_pages(A, 255);  
    cprintf("全部释放\n");
    cprintf("检查完成，没有错误\n");
}
// 这个结构体在
const struct pmm_manager buddy_pmm_manager = {//接口结构体
    .name = "buddy_pmm_manager",
    .init = buddy_system_init,
    .init_memmap = buddy_system_init_memmap,
    .alloc_pages = buddy_system_alloc_pages,
    .free_pages = buddy_system_free_pages,
    .nr_free_pages = buddy_system_nr_free_pages,
    .check = buddy_check,
};
